52C - Circular RMQ - CodeForces Solution

#include "bits/stdc++.h"
using namespace std;

typedef long long LL;
typedef vector<LL> vi;
class SegmentTree {
private:
    LL n;
    vi A, st, lazy;

    LL l(LL p) { return  p << 1; }
    LL r(LL p) { return (p << 1) + 1; }

    LL conquer(LL a, LL b) { return min(a, b); }

    void build(LL p, LL L, LL R) {
        if (L == R)
            st[p] = A[L];
        else {
            LL m = (L + R) / 2;
            build(l(p), L, m);
            build(r(p), m + 1, R);
            st[p] = conquer(st[l(p)], st[r(p)]);
        }
    }

    void propagate(LL p, LL L, LL R) {
        st[p] += lazy[p];
        if (L != R) lazy[l(p)] += lazy[p], lazy[r(p)] += lazy[p];
        else A[L] += lazy[p];
        lazy[p] = 0;
    }

    LL RMQ(LL p, LL L, LL R, LL i, LL j) {
        propagate(p, L, R);
        if (i > j) return LLONG_MAX;
        if ((L >= i) && (R <= j)) return st[p];
        LL m = (L + R) / 2;
        return conquer(RMQ(l(p), L, m, i, min(m, j)),
            RMQ(r(p), m + 1, R, max(i, m + 1), j));
    }

    void update(LL p, LL L, LL R, LL i, LL j, LL val) {
        propagate(p, L, R);
        if (i > j) return;
        if ((L >= i) && (R <= j)) {
            lazy[p] += val;
            propagate(p, L, R);
        }
        else {
            LL m = (L + R) / 2;
            update(l(p), L, m, i, min(m, j), val);
            update(r(p), m + 1, R, max(i, m + 1), j, val);
            st[p] = min(st[l(p)], st[r(p)]);
        }
    }

public:
    SegmentTree(LL sz) : n(sz), st(4 * n), lazy(4 * n) {}

    SegmentTree(const vi& initialA) : SegmentTree((LL)initialA.size()) {
        A = initialA;
        build(1, 0, n - 1);
    }

    void update(LL i, LL j, LL val) { update(1, 0, n - 1, i, j, val); }

    LL RMQ(LL i, LL j) { return RMQ(1, 0, n - 1, i, j); }
};

int main() {
    {ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);}

    long long n, m, val;
    cin >> n; vector<LL>v(n);
    for (LL i = 0; i < n; i++)cin >> v[i];
    SegmentTree st(v);
    cin >> m;
    string s;
    getline(cin, s);
    while (m--) {
        vector<LL> qs;
        getline(cin, s);
        stringstream ss(s);
        while (ss >> val)qs.push_back(val);
        if (qs.size() == 2) {
            if (qs[0] <= qs[1])cout << st.RMQ(qs[0], qs[1]) << "\n";
            else cout << min(st.RMQ(0, qs[1]), st.RMQ(qs[0], n - 1)) << "\n";
        }
        else {
            if (qs[0] <= qs[1])st.update(qs[0], qs[1], qs[2]);
            else st.update(0, qs[1], qs[2]), st.update(qs[0], n - 1, qs[2]);
        }
    }

    return 0;
}